package com.sheng.leetcode.year2022.month08.day27;

import org.junit.Test;

import java.util.*;

/**
 * @author liusheng
 * @date 2022/08/29
 *
 * 662. 二叉树最大宽度
 *
 * 给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
 * 树的 最大宽度 是所有层中最大的 宽度 。
 * 每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，
 * 两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
 * 题目数据保证答案将会在  32 位 带符号整数范围内。
 *
 * 示例 1：
 * 输入：root = [1,3,2,5,3,null,9]
 * 输出：4
 * 解释：最大宽度出现在树的第 3 层，宽度为 4 (5,3,null,9) 。
 *
 * 示例 2：
 * 输入：root = [1,3,2,5,null,null,9,6,null,7]
 * 输出：7
 * 解释：最大宽度出现在树的第 4 层，宽度为 7 (6,null,null,null,null,null,7) 。
 *
 * 示例 3：
 * 输入：root = [1,3,2,5]
 * 输出：2
 * 解释：最大宽度出现在树的第 2 层，宽度为 2 (3,2) 。
 *
 * 提示：
 *
 * 树中节点的数目范围是 [1, 3000]
 * -100 <= Node.val <= 100
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/maximum-width-of-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0662 {

    @Test
    public void test01() {
//        TreeNode root = new TreeNode(1);
//        TreeNode left = new TreeNode(3);
//        TreeNode right = new TreeNode(2);
//        left.left = new TreeNode(5);
//        left.right = new TreeNode(3);
//        right.right = new TreeNode(9);
//        root.left = left;
//        root.right = right;

        TreeNode root = new TreeNode(1);
        TreeNode left = new TreeNode(3);
        TreeNode right = new TreeNode(2);
        TreeNode left1 = new TreeNode(5);
        left1.left = new TreeNode(6);
        left.left = left1;
        TreeNode right1 = new TreeNode(9);
        right1.left = new TreeNode(7);
        right.right = right1;
        root.left = left;
        root.right = right;
        System.out.println(new Solution().widthOfBinaryTree(root));
    }
}

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

//class Solution {
//    int max = 0;
//    public int widthOfBinaryTree(TreeNode root) {
//        // 需要获取每一层的“宽度”，然后求出最大宽度，层序遍历（超时）
//        List<TreeNode> arrayList = new ArrayList<>();
//        arrayList.add(root);
//        bfs(arrayList);
//        return max;
//    }
//
//    public void bfs(List<TreeNode> list) {
//        max = Math.max(max, list.size());
//        List<TreeNode> arrayList = new ArrayList<>();
//        List<TreeNode> temp = new ArrayList<>();
//        for (TreeNode treeNode : list) {
//            if (treeNode.left != null) {
//                temp.add(treeNode.left);
//            }
//            if (treeNode.right != null) {
//                temp.add(treeNode.right);
//            }
//        }
//        if (temp.size() > 0) {
//            // 获取左右端点
//            TreeNode left = temp.get(0);
//            TreeNode right = temp.get(temp.size() - 1);
//            for (TreeNode treeNode : list) {
//                if (treeNode.left != null) {
//                    arrayList.add(treeNode.left);
//                } else {
//                    // 如果端点位于左右端点之间，并且为null，那么也需要放进去
//                    if (arrayList.contains(left) && !arrayList.contains(right)) {
//                        arrayList.add(new TreeNode());
//                    }
//                }
//                if (treeNode.right != null) {
//                    arrayList.add(treeNode.right);
//                } else {
//                    if (arrayList.contains(left) && !arrayList.contains(right)) {
//                        arrayList.add(new TreeNode());
//                    }
//                }
//            }
//            if (arrayList.size() > 0) {
//                bfs(arrayList);
//            }
//        }
//    }
//}

//根据满二叉树的节点编号规则：若根节点编号为 u，则其左子节点编号为 u << 1，其右节点编号为 u << 1 | 1。
//一个朴素的想法是：我们在 DFS过程中使用两个哈希表分别记录每层深度中的最小节点编号和最大节点编号，两者距离即是当前层的宽度，最终所有层数中的最大宽度即是答案。
//而实现上，我们可以利用先 DFS 左节点，再 DFS 右节点的性质可知，每层的最左节点必然是最先被遍历到，
//因此我们只需要记录当前层最先被遍历到点编号（即当前层最小节点编号），并在 DFS 过程中计算宽度，更新答案即可。
//看到评论区有同学讨论关于编号溢出问题，之所以溢出仍能 AC 是因为测试数组中没有同层内「宽度」左端点不溢出，右端点溢出，同时该层就是最大宽度的数据点。
//我们可以通过 u = u - map.get(depth) + 1 操作来对同层内的节点进行重新编号（使得同层最靠左的非空节点编号为 1）。
//通过重编号操作 我们可以消除由于深度加深带来的编号溢出问题，同时 TS 代码不再需要使用 bigint。
//
//代码：
//
class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    int ans;
    public int widthOfBinaryTree(TreeNode root) {
        dfs(root, 1, 0);
        return ans;
    }

    /**
     * 深度遍历
     *
     * @param root 结点
     * @param u 结点的编号
     * @param depth 深度
     */
    void dfs(TreeNode root, int u, int depth) {
        // 如果结点为null，直接返回
        if (root == null) {
            return ;
        }
        // 如果当前深度不存在于map集合中，则以当前结点所在深度depth为key，结点编号u为value
        if (!map.containsKey(depth)) {
            map.put(depth, u);
        }
        // 将最大宽度ans和 当前结点编号减去当前结点所在深度对应的编号值再加一 进行比较，取最大的赋值给ans
        ans = Math.max(ans, u - map.get(depth) + 1);
        u = u - map.get(depth) + 1;
        // 满二叉树的节点编号规则：若根节点编号为 u，则其左子节点编号为 u << 1，其右节点编号为 u << 1 | 1
        // 遍历左结点
        dfs(root.left, u << 1, depth + 1);
        // 遍历右结点
        dfs(root.right, u << 1 | 1, depth + 1);
    }
}
//
//作者：AC_OIer
//链接：https://leetcode.cn/problems/maximum-width-of-binary-tree/solution/by-ac_oier-33er/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
